package q932_beautifulArray;

import java.util.HashMap;
import java.util.Map;

public class Solution {
    /*
    另一个分治的典型题
    对于漂亮数组的定义有些晦涩，但是只需要注重每一个数字的映射关系即可
     */
    Map<Integer, int[]> memo;
    public int[] beautifulArray(int N) {
        memo = new HashMap< Integer, int[]>();
        memo.put(1, new int[]{1});
        return f(N);
    }

    private int[] f(int n) {
        if (!memo.containsKey(n)) {
            int[] res = new int[n];
            int index = 0;
            for (int i : f((n + 1) / 2)) {
                res[index++] = 2 * i - 1;
            }
            for (int i : f(n / 2)) {
                res[index++] = 2 * i;
            }
            memo.put(n, res);
        }
        return memo.get(n);
    }
}
